#include <iostream>
#include <string>
using namespace std;
class Solution {
    public:
        class bigest
        {
            public:
                bigest():start(0), end(0){}
                int start;
                int end;
        };
        string longestPalindrome(string s) 
        {
            bigest bg;
            
            for(int i = 0; i < s.size(); i++)
            {
                if (s.size() - i < bg.end - bg.start)
                    break;
                for (int j = s.size() - 1; j > i; j--)
                {
                    // find bigest ch start pos = i  end pos = j
                    int begin = i ;
                    int end = j;
                    while(end > begin)
                    {
                        if (!(s.at(end) ^ s.at(begin)))
                        {
                            begin++;
                            end--;
                        }
                        else
                            break;
                    }
                    if (end <= begin)
                        if (j - i > bg.end - bg.start)
                        {
                            bg.end = j;
                            bg.start = i;
                        }
                }
            } 
            return s.substr(bg.start, bg.end - bg.start + 1);
        }
};

int main()
{
    Solution s;
    {
        string test = "abbba";
        cout <<"Source" << test << "\t" <<  s.longestPalindrome(test) << endl;
    }
    {
        string test = "babad";
        cout <<"Source" << test << "\t" <<  s.longestPalindrome(test) << endl;
    }
    {
        string test = "b";
        cout <<"Source" << test << "\t" <<  s.longestPalindrome(test) << endl;
    }
    {
        string test = "abcda";
        cout <<"Source" << test << "\t" <<  s.longestPalindrome(test) << endl;
    }
    {
        string test = "aaaaa";
        cout <<"Source" << test << "\t" <<  s.longestPalindrome(test) << endl;
    }
    return 0;
}
